package datastructure.tree.bst;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @Description: 二叉搜索树, 这个数可以比较, 所以我们数的元素继承Comparable接口
 * @author: Yang Qiang
 * @create: 2021-12-01 21:00
 */
public class BSTree<E extends Comparable<E>> {

    // 树的根节点
    private Node root;
    // 树的节点个数
    private int size;

    // 删除节点
    public void remove(E e){
        root = remove(root, e);
    }

    /**
     *
     * @param node: 以node为根的树删除元素e
     * @param e: 需要删除的元素
     * @return: 返回删除了元素e之后的新树的根节点
     */
    public Node remove(Node node, E e){
        if (node == null) return null;
        // 如果删除节点小于根节点, 就往根节点的左子树继续删除
        if (e.compareTo(node.e) < 0){
            node.left = remove(node.left, e);
            return node;
        }
        // 如果删除节点大于根节点, 就往根节点的右子树继续删除
        else if (e.compareTo(node.e) > 0){
            node.right = remove(node.right, e);
            return node;
        }
        // 最后一种情况就是相等也就是该删除了, 删除的时候有三种情况
        else {
            // 第一种情况: 删除的节点没有左子节点
            if (node.left == null){
                // 先拿到右节点
                Node rightNode = node.right;
                // 再把需要删除节点的右节点置为null, 也就删除了
                node.right = null;
                size--;
                // 然后返回右节点, 也就是把这个右节点作为根节点代替删除的节点
                return rightNode;
            }
            // 第二种情况:删除的节点没有右子节点
            if (node.right == null){
                // 先拿到左节点
                Node leftNode = node.left;
                // 再把需要删除节点的左节点置为null, 也就删除了
                node.left = null;
                size--;
                // 然后返回右节点, 也就是把这个右节点作为根节点代替删除的节点
                return leftNode;
            }
            // 第三种情况: 有两颗左右子节点
            // 这种情况的删除思路: 可以拿右边最小节点, 或者左边最大节点来替换, 我们拿右最小
            // 找到右子树最小节点
            Node minNode = minNode(node.right);
            // 删除节点, 并且拿最小节点来替换
            minNode.right = remove(node.right, minNode.e);
            // 替换
            minNode.left = node.left;
            node.left=node.right=null;
            return minNode;

        }
    }
    // 找右子子树最小节点
    private Node minNode(Node node) {
        if (node.left == null) return node;
        return minNode(node.left);
    }


    /**
     * 广度优先-层级遍历
     */
    public void levelOrder(){
        if (root == null) return;
        // 声明一个队列
        LinkedList<Node> queue = new LinkedList<>();
        // 根节点入队
        queue.add(root);
        // 队列不为null就一直操作
        while (!queue.isEmpty()){
            // 根节点出队
            Node node = queue.remove();
            System.out.println(node.e);
            // 判断根节点是否有左右节点, 有的话就入队
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);

        }
    }


    /**
     * 非递归前序遍历
     */
    public void preOrderNoDiGui(){
        if (root == null) return;
        // 创建一个栈
        Stack<Node> stack = new Stack<>();
        // 根节点入栈
        stack.push(root);
        // 栈不为null, 就一直循环
        while (!stack.isEmpty()){
            // 根节点出栈
            Node curNode = stack.pop();
            System.out.println(curNode.e);
            // 判断是否有左右子节点, 有的话就入栈, 并且是右先入栈, 左后入栈
            if (curNode.right != null) stack.push(curNode.right);
            if (curNode.left != null) stack.push(curNode.left);
        }
    }


    // 深度优先-后续遍历
    public void afterOrder(){
        afterOrder(root);
    }
    /**
     * 以node为根节点的二叉搜索树的后续遍历
     * @param node
     */
    private void afterOrder(Node node) {
        if (node == null) return;
        // 先遍历左子树
        afterOrder(node.left);
        // 再遍历右子树
        afterOrder(node.right);
        // 输出父节点
        System.out.println(node.e);
    }

    // 深度优先-中序遍历
    public void minOrder(){
        minOrder(root);
    }
    /**
     * 以node为根节点的二叉搜索树的中序遍历
     * @param node
     */
    private void minOrder(Node node) {
        if (node == null) return;
        // 先遍历左子树
        minOrder(node.left);
        // 再输出父节点
        System.out.println(node.e);
        // 再遍历右子树
        minOrder(node.right);

    }


    // 深度优先-前序遍历
    public void preOrder(){
        preOrder(root);
    }
    /**
     * 以node为根节点的二叉搜索树的前序遍历
     * @param node
     */
    private void preOrder(Node node) {
        if (node == null) return;
        // 先输出根节点数据
        System.out.println(node.e);
        // 再遍历左子树->递归
        preOrder(node.left);
        // 再遍历右子树
        preOrder(node.right);
    }


    // 搜索元素e所在节点的父节点
    public Node searchParentEle(E e){
        return searchParentEle(root, e);
    }
    /**
     * 以node为根节点查找元素e节点的父节点
     * 思路: 如果查找的这个node节点有左子树, 就直接拿这个左子树的根节点的元素等于e吗, 等于的话node就是父节点
     *       如果查找的这个node节点有右子树, 就直接拿这个右子树的根节点的元素等于e吗, 等于的话node就是父节点
     * @param node
     * @param e
     * @return
     */
    private Node searchParentEle(Node node, E e) {
        if (node == null) return null;
        // 如果节点的左右节点不为null, 或者左右节点有一个节点的元素等于了e, 那么就找到了
        if ((node.left!=null && e.compareTo(node.left.e)==0) || (node.right!=null && e.compareTo(node.right.e)==0)){
            return node;
        }else {
            if (node.left != null && e.compareTo(node.e) < 0) {// 如果节点的左节点不为null并且e小于节点元素就往左边继续找
                return searchParentEle(node.left, e);
            } else if (node.right != null && e.compareTo(node.e) > 0) {// 如果节点的左节点不为null并且e大于节点元素就往右边继续找
                return searchParentEle(node.right, e);
            }
        }
        return null;
    }


    // 搜索元素e所在的节点
    public Node searchEle(E e){
       return searchEle(root, e);
    }
    /**
     * 以node为跟节点的树中查找元素为e的节点
     * @param node 从搜索二叉树的根节点开始找
     * @param e
     * @return 元素所在的节点
     */
    private Node searchEle(Node node, E e) {
        if (node == null) return null;
        if (node.e == e){// 元素相等就返回
            return node;
        }else if (e.compareTo(node.e) < 1){// 查找的元素比当前节点元素小, 往左边继续找
            return searchEle(node.left, e);
        }else {// 查找的元素比当前节点元素大, 往右边继续找
            return searchEle(node.right, e);
        }
    }


    // 添加节点, 构建BST树
    public void addEle(E e){
        this.root = addEle(root, e);
    }
    /**
     * 将元素e插入到以node为根节点的子树
     * @param node
     * @param e
     * @return: 新插入了元素e以后新数的根
     */
    private Node addEle(Node node, E e){
        // 如果是一个空树 || 递归到最后一个没有子节点的节点
        if (node == null){
            size++;
            return new Node(e);
        }
        // 如果树里面有元素
        if (e.compareTo(node.e) < 1){// 如果添加的元素比节点小就插入左边, 但是左边需要一直递归
            node.left = addEle(node.left, e);
        }else {// 如果添加的元素大于等于节点就插入右边, 但是右边需要一直递归
            node.right = addEle(node.right, e);
        }
        return node;
    }

    public int getSize() {
        return size;
    }

    // 树节点
    private class Node{
        // 节点的数据
        public E e;
        // 节点的左节点
        public Node left;
        // 节点的右节点
        public Node right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
        public Node() {
        }
        @Override
        public String toString() {
            return e + "";
        }
    }
}
